import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        System.out.println(new Solution().wiggleMaxLength(new int[]{1,7,4,9,2,5}));
        System.out.println(new Solution().wiggleMaxLength(new int[]{1,1,1,7,4,9,2,5}));
        System.out.println(new Solution().wiggleMaxLength(new int[]{1,17,5,10,13,15,10,5,16,8}));
        System.out.println(new Solution().wiggleMaxLength(new int[]{1,2,3,4,5,6,7,8,9}));
    }
}

//贪心
class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length == 1) {
            return 1;
        }
        int count = 1;
        int prevDiff = 0;
        for (int i = 1; i < nums.length; i++) {
            int diff = nums[i] - nums[i - 1];
            if (prevDiff == 0) {
                if (diff == 0) {
                    continue;
                }
                prevDiff = diff;
                count++;
                continue;
            }
            if (prevDiff * diff != 0) {
                if (prevDiff * diff < 0) {
                    count++;
                }
                prevDiff = diff;
            }
        }
        return count;
    }
}

//贪心代码优化（题解）
class Solution1 {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length == 1) {
            return 1;
        }
        int count = 1;
        int prevDiff = 0;
        for (int i = 1; i < nums.length; i++) {
            int diff = nums[i] - nums[i - 1];
            if (prevDiff <= 0 && diff > 0 || prevDiff >= 0 && diff < 0) {
                count++;
                prevDiff = diff;
            }
        }
        return count;
    }
}

//动态规划代码最优化（题解）
class Solution2 {
    public int wiggleMaxLength(int[] nums) {
        int up = 1, down = 1;
        for (int i = 1; i < nums.length; i++) {
            int diff = nums[i] - nums[i - 1];
            if (diff > 0) {
                up = down + 1;
            } else if (diff < 0) {
                down = up + 1;
            }
        }
        return Math.max(up, down);
    }
}